//
// Description: 并查集模板
// Created by Loading on 2021/7/25.
//

/* 适用于个体合并成集体，并求集体的个数问题 */

// 例题：547. 省份数量

#include <bits/stdc++.h>

using namespace std;

const int N = 100; // 数据量
int father[N];     // 集 （父节点集合）

// 初始化
void Init(int n) {
    // 在合并之前初始化每个节点为该集合的根节点（每个数都是一个集合，自己的父节点初始化为自己）
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

// 查
int FindFather(int x) {
    /* 功能：找到元素x在该集合中的根节点（根节点满足x == father[x]） */

    if (x != father[x]) {
        /* 路径压缩 */
        father[x] = FindFather(father[x]);
    }
    return father[x];

//    // 记录初始节点
//    int a = x;
//    // 循环查找父节点，找到集合的根节点
//    while (x != father[x]) {
//        x = father[x];   // 循环结束后的 x 为该集合的根节点
//    }
//    /* 路径压缩，将寻找根节点路途中的每个节点指向其根节点，优化之后的查找速度，可不写 */
//    while (a != father[a]) {
//        int b = a;      // 记录 a，防止后面被覆盖
//        a = father[a];  // 让 a 指向其父节点
//        father[b] = x;  // 指向根节点
//    }
//    return x;
}

// 并
void Union(int a, int b) {
    /* 功能：将 a 与 b 合并到一个集合中 */

    // 分别找到 a, b 所在结合的根节点
    int Ra = FindFather(a);
    int Rb = FindFather(b);
    // 当 a, b 不在同一个集合中时将 Ra 指向 Rb，或者将 Rb 指向 Ra （选择一个作为根节点）
    if (Ra != Rb) {
        // 将 Ra 指向 Rb
        father[Ra] = Rb;
        // father[Rb] = Ra; 也可以
    }
}

int main() {

}